package com.my.code.sort;

import java.util.Arrays;

import static com.my.code.sort.Util.swap;

/**
 * 快速排序实现：双指针法<br/>
 * 快速排序是使用基准数将一个数组拆分成两个子数组，如此递归拆分，也是分治思想的运用
 * <p>
 * 参考 https://blog.csdn.net/afjaklsdflka/article/details/52829030
 *
 * @author zzl
 * @date 2020/10/15
 */
public class QuickSort2 {

    public static void main(String[] args) {
        //int[] arr = {5, 7, 1, 6, 4, 8, 3, 2};
        int[] arr = {6, 7, 3, 1, 5, 4};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr, int start, int end) {
        if (start < end) {
            int i = split(arr, start, end);
            sort(arr, start, i - 1);
            sort(arr, i + 1, end);
        }
    }

    /**
     * 分处理，从起始到结束，根据对比数将左右比较并交换
     *
     * @param start 起始位置
     * @param end   结束位置
     */
    private static int split(int[] arr, int start, int end) {
        int base = arr[start];//比较基准数
        int i = start, j = end;
        while (i < j) {
            while (i < j && arr[j] >= base) j--;//从右到左找到第一个小于比较元素的数
            while (i < j && arr[i] <= base) i++;//从左到右找到第一个大于比较元素的数
            if (i != j) swap(arr, i, j);
        }
        swap(arr, i, start);//将比较元素交换到期望位置
        return i;
    }

}
